home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 25 / CU Amiga Magazine's Super CD-ROM 25 (1998)(EMAP Images)(GB)(Track 1 of 2)[!][issue 1998-08].iso / CUCD / Programming / ixemul / sdk / man / cat3 / queue.0 < prev    next >
Encoding:
Text File  |  1998-06-15  |  15.4 KB  |  315 lines
  1.  
  2. QUEUE(3)                   UNIX Programmer's Manual                   QUEUE(3)
  3.  
  4. NNAAMMEE
  5.      LLIISSTT__EENNTTRRYY, LLIISSTT__HHEEAADD, LLIISSTT__IINNIITT, LLIISSTT__IINNSSEERRTT__AAFFTTEERR, LLIISSTT__IINNSSEERRTT__BBEEFFOORREE,
  6.      LLIISSTT__IINNSSEERRTT__HHEEAADD, LLIISSTT__RREEMMOOVVEE, TTAAIILLQQ__EENNTTRRYY, TTAAIILLQQ__HHEEAADD, TTAAIILLQQ__IINNIITT,
  7.      TTAAIILLQQ__IINNSSEERRTT__AAFFTTEERR, TTAAIILLQQ__IINNSSEERRTT__BBEEFFOORREE, TTAAIILLQQ__IINNSSEERRTT__HHEEAADD,
  8.      TTAAIILLQQ__IINNSSEERRTT__TTAAIILL, TTAAIILLQQ__RREEMMOOVVEE, CCIIRRCCLLEEQQ__EENNTTRRYY, CCIIRRCCLLEEQQ__HHEEAADD,
  9.      CCIIRRCCLLEEQQ__IINNIITT, CCIIRRCCLLEEQQ__IINNSSEERRTT__AAFFTTEERR, CCIIRRCCLLEEQQ__IINNSSEERRTT__BBEEFFOORREE,
  10.      CCIIRRCCLLEEQQ__IINNSSEERRTT__HHEEAADD, CCIIRRCCLLEEQQ__IINNSSEERRTT__TTAAIILL, CCIIRRCCLLEEQQ__RREEMMOOVVEE - implementa-
  11.      tions of lists, tail queues, and circular queues
  12.  
  13. SSYYNNOOPPSSIISS
  14.      ##iinncclluuddee <<ssyyss//qquueeuuee..hh>>
  15.  
  16.  
  17.      LLIISSTT__EENNTTRRYY(_T_Y_P_E)
  18.  
  19.      LLIISSTT__HHEEAADD(_H_E_A_D_N_A_M_E, _T_Y_P_E)
  20.  
  21.      LLIISSTT__IINNIITT(_L_I_S_T___H_E_A_D _*_h_e_a_d)
  22.  
  23.      LLIISSTT__IINNSSEERRTT__AAFFTTEERR(_T_Y_P_E _*_l_i_s_t_e_l_m, _T_Y_P_E _*_e_l_m, _L_I_S_T___E_N_T_R_Y _N_A_M_E)
  24.  
  25.      LLIISSTT__IINNSSEERRTT__BBEEFFOORREE(_T_Y_P_E _*_l_i_s_t_e_l_m, _T_Y_P_E _*_e_l_m, _L_I_S_T___E_N_T_R_Y _N_A_M_E)
  26.  
  27.      LLIISSTT__IINNSSEERRTT__HHEEAADD(_L_I_S_T___H_E_A_D _*_h_e_a_d, _T_Y_P_E _*_e_l_m, _L_I_S_T___E_N_T_R_Y _N_A_M_E)
  28.  
  29.      LLIISSTT__RREEMMOOVVEE(_T_Y_P_E _*_e_l_m, _L_I_S_T___E_N_T_R_Y _N_A_M_E)
  30.  
  31.  
  32.      TTAAIILLQQ__EENNTTRRYY(_T_Y_P_E)
  33.  
  34.      TTAAIILLQQ__HHEEAADD(_H_E_A_D_N_A_M_E, _T_Y_P_E)
  35.  
  36.      TTAAIILLQQ__IINNIITT(_T_A_I_L_Q___H_E_A_D _*_h_e_a_d)
  37.  
  38.      TTAAIILLQQ__IINNSSEERRTT__AAFFTTEERR(_T_A_I_L_Q___H_E_A_D _*_h_e_a_d, _T_Y_P_E _*_l_i_s_t_e_l_m, _T_Y_P_E _*_e_l_m,
  39.              _T_A_I_L_Q___E_N_T_R_Y _N_A_M_E)
  40.  
  41.      TTAAIILLQQ__IINNSSEERRTT__BBEEFFOORREE(_T_Y_P_E _*_l_i_s_t_e_l_m, _T_Y_P_E _*_e_l_m, _T_A_I_L_Q___E_N_T_R_Y _N_A_M_E)
  42.  
  43.      TTAAIILLQQ__IINNSSEERRTT__HHEEAADD(_T_A_I_L_Q___H_E_A_D _*_h_e_a_d, _T_Y_P_E _*_e_l_m, _T_A_I_L_Q___E_N_T_R_Y _N_A_M_E)
  44.  
  45.      TTAAIILLQQ__IINNSSEERRTT__TTAAIILL(_T_A_I_L_Q___H_E_A_D _*_h_e_a_d, _T_Y_P_E _*_e_l_m, _T_A_I_L_Q___E_N_T_R_Y _N_A_M_E)
  46.  
  47.      TTAAIILLQQ__RREEMMOOVVEE(_T_A_I_L_Q___H_E_A_D _*_h_e_a_d, _T_Y_P_E _*_e_l_m, _T_A_I_L_Q___E_N_T_R_Y _N_A_M_E)
  48.  
  49.  
  50.      CCIIRRCCLLEEQQ__EENNTTRRYY(_T_Y_P_E)
  51.  
  52.      CCIIRRCCLLEEQQ__HHEEAADD(_H_E_A_D_N_A_M_E, _T_Y_P_E)
  53.  
  54.      CCIIRRCCLLEEQQ__IINNIITT(_C_I_R_C_L_E_Q___H_E_A_D _*_h_e_a_d)
  55.  
  56.      CCIIRRCCLLEEQQ__IINNSSEERRTT__AAFFTTEERR(_C_I_R_C_L_E_Q___H_E_A_D _*_h_e_a_d, _T_Y_P_E _*_l_i_s_t_e_l_m, _T_Y_P_E _*_e_l_m,
  57.              _C_I_R_C_L_E_Q___E_N_T_R_Y _N_A_M_E)
  58.  
  59.      CCIIRRCCLLEEQQ__IINNSSEERRTT__BBEEFFOORREE(_C_I_R_C_L_E_Q___H_E_A_D _*_h_e_a_d, _T_Y_P_E _*_l_i_s_t_e_l_m, _T_Y_P_E _*_e_l_m,
  60.              _C_I_R_C_L_E_Q___E_N_T_R_Y _N_A_M_E)
  61.  
  62.      CCIIRRCCLLEEQQ__IINNSSEERRTT__HHEEAADD(_C_I_R_C_L_E_Q___H_E_A_D _*_h_e_a_d, _T_Y_P_E _*_e_l_m, _C_I_R_C_L_E_Q___E_N_T_R_Y _N_A_M_E)
  63.  
  64.      CCIIRRCCLLEEQQ__IINNSSEERRTT__TTAAIILL(_C_I_R_C_L_E_Q___H_E_A_D _*_h_e_a_d, _T_Y_P_E _*_e_l_m, _C_I_R_C_L_E_Q___E_N_T_R_Y _N_A_M_E)
  65.  
  66.  
  67.      CCIIRRCCLLEEQQ__RREEMMOOVVEE(_C_I_R_C_L_E_Q___H_E_A_D _*_h_e_a_d, _T_Y_P_E _*_e_l_m, _C_I_R_C_L_E_Q___E_N_T_R_Y _N_A_M_E)
  68.  
  69. DDEESSCCRRIIPPTTIIOONN
  70.      These macros define and operate on three types of data structures: lists,
  71.      tail queues, and circular queues.  All three structures support the fol-
  72.      lowing functionality:
  73.            1.   Insertion of a new entry at the head of the list.
  74.            2.   Insertion of a new entry before or after any element in the
  75.                 list.
  76.            3.   Removal of any entry in the list.
  77.            4.   Forward traversal through the list.
  78.  
  79.      Lists are the simplest of the three data structures and support only the
  80.      above functionality.
  81.  
  82.      Tail queues add the following functionality:
  83.            1.   Entries can be added at the end of a list.
  84.      However:
  85.            1.   All list insertions and removals, except insertion before an-
  86.                 other element, must specify the head of the list.
  87.            2.   Each head entry requires two pointers rather than one.
  88.            3.   Code size is about 15% greater and operations run about 20%
  89.                 slower than lists.
  90.  
  91.      Circular queues add the following functionality:
  92.            1.   Entries can be added at the end of a list.
  93.            2.   They may be traversed backwards, from tail to head.
  94.      However:
  95.            1.   All list insertions and removals must specify the head of the
  96.                 list.
  97.            2.   Each head entry requires two pointers rather than one.
  98.            3.   The termination condition for traversal is more complex.
  99.            4.   Code size is about 40% greater and operations run about 45%
  100.                 slower than lists.
  101.  
  102.      In the macro definitions, _T_Y_P_E is the name of a user defined structure,
  103.      that must contain a field of type LIST_ENTRY, TAILQ_ENTRY, or
  104.      CIRCLEQ_ENTRY, named _N_A_M_E. The argument _H_E_A_D_N_A_M_E is the name of a user
  105.      defined structure that must be declared using the macros LIST_HEAD,
  106.      TAILQ_HEAD, or CIRCLEQ_HEAD. See the examples below for further explana-
  107.      tion of how these macros are used.
  108.  
  109. LLIISSTTSS
  110.      A list is headed by a structure defined by the LLIISSTT__HHEEAADD macro.  This
  111.      structure contains a single pointer to the first element on the list.
  112.      The elements are doubly linked so that an arbitrary element can be re-
  113.      moved without traversing the list.  New elements can be added to the list
  114.      after an existing element, before an existing element, or at the head of
  115.      the list.  A _L_I_S_T___H_E_A_D structure is declared as follows:
  116.  
  117.            LIST_HEAD(HEADNAME, TYPE) head;
  118.  
  119.      where _H_E_A_D_N_A_M_E is the name of the structure to be defined, and _T_Y_P_E is
  120.      the type of the elements to be linked into the list.  A pointer to the
  121.      head of the list can later be declared as:
  122.  
  123.            struct HEADNAME *headp;
  124.  
  125.      (The names head and headp are user selectable.)
  126.  
  127.      The macro LLIISSTT__EENNTTRRYY declares a structure that connects the elements in
  128.      the list.
  129.  
  130.      The macro LLIISSTT__IINNIITT initializes the list referenced by _h_e_a_d.
  131.  
  132.  
  133.      The macro LLIISSTT__IINNSSEERRTT__HHEEAADD inserts the new element _e_l_m at the head of the
  134.      list.
  135.  
  136.      The macro LLIISSTT__IINNSSEERRTT__AAFFTTEERR inserts the new element _e_l_m after the element
  137.      _l_i_s_t_e_l_m.
  138.  
  139.      The macro LLIISSTT__IINNSSEERRTT__BBEEFFOORREE inserts the new element _e_l_m before the ele-
  140.      ment _l_i_s_t_e_l_m.
  141.  
  142.      The macro LLIISSTT__RREEMMOOVVEE removes the element _e_l_m from the list.
  143.  
  144. LLIISSTT EEXXAAMMPPLLEE
  145.      LIST_HEAD(listhead, entry) head;
  146.      struct listhead *headp;         /* List head. */
  147.      struct entry {
  148.              ...
  149.              LIST_ENTRY(entry) entries;      /* List. */
  150.              ...
  151.      } *n1, *n2, *np;
  152.  
  153.      LIST_INIT(&head);                       /* Initialize the list. */
  154.  
  155.      n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
  156.      LIST_INSERT_HEAD(&head, n1, entries);
  157.  
  158.      n2 = malloc(sizeof(struct entry));      /* Insert after. */
  159.      LIST_INSERT_AFTER(n1, n2, entries);
  160.  
  161.      n2 = malloc(sizeof(struct entry));      /* Insert before. */
  162.      LIST_INSERT_BEFORE(n1, n2, entries);
  163.                                              /* Forward traversal. */
  164.      for (np = head.lh_first; np != NULL; np = np->entries.le_next)
  165.              np-> ...
  166.  
  167.      while (head.lh_first != NULL)           /* Delete. */
  168.              LIST_REMOVE(head.lh_first, entries);
  169.  
  170. TTAAIILL QQUUEEUUEESS
  171.      A tail queue is headed by a structure defined by the TTAAIILLQQ__HHEEAADD macro.
  172.      This structure contains a pair of pointers, one to the first element in
  173.      the tail queue and the other to the last element in the tail queue.  The
  174.      elements are doubly linked so that an arbitrary element can be removed
  175.      without traversing the tail queue.  New elements can be added to the
  176.      queue after an existing element, before an existing element, at the head
  177.      of the queue, or at the end the queue.  A _T_A_I_L_Q___H_E_A_D structure is de-
  178.      clared as follows:
  179.  
  180.            TAILQ_HEAD(HEADNAME, TYPE) head;
  181.  
  182.      where HEADNAME is the name of the structure to be defined, and TYPE is
  183.      the type of the elements to be linked into the tail queue.  A pointer to
  184.      the head of the tail queue can later be declared as:
  185.  
  186.            struct HEADNAME *headp;
  187.  
  188.      (The names head and headp are user selectable.)
  189.  
  190.      The macro TTAAIILLQQ__EENNTTRRYY declares a structure that connects the elements in
  191.      the tail queue.
  192.  
  193.      The macro TTAAIILLQQ__IINNIITT initializes the tail queue referenced by _h_e_a_d.
  194.  
  195.      The macro TTAAIILLQQ__IINNSSEERRTT__HHEEAADD inserts the new element _e_l_m at the head of
  196.      the tail queue.
  197.  
  198.  
  199.      The macro TTAAIILLQQ__IINNSSEERRTT__TTAAIILL inserts the new element _e_l_m at the end of the
  200.      tail queue.
  201.  
  202.      The macro TTAAIILLQQ__IINNSSEERRTT__AAFFTTEERR inserts the new element _e_l_m after the ele-
  203.      ment _l_i_s_t_e_l_m.
  204.  
  205.      The macro TTAAIILLQQ__IINNSSEERRTT__BBEEFFOORREE inserts the new element _e_l_m before the ele-
  206.      ment _l_i_s_t_e_l_m.
  207.  
  208.      The macro TTAAIILLQQ__RREEMMOOVVEE removes the element _e_l_m from the tail queue.
  209.  
  210. TTAAIILL QQUUEEUUEE EEXXAAMMPPLLEE
  211.      TAILQ_HEAD(tailhead, entry) head;
  212.      struct tailhead *headp;         /* Tail queue head. */
  213.      struct entry {
  214.              ...
  215.              TAILQ_ENTRY(entry) entries;     /* Tail queue. */
  216.              ...
  217.      } *n1, *n2, *np;
  218.  
  219.      TAILQ_INIT(&head);                      /* Initialize the queue. */
  220.  
  221.      n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
  222.      TAILQ_INSERT_HEAD(&head, n1, entries);
  223.  
  224.      n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
  225.      TAILQ_INSERT_TAIL(&head, n1, entries);
  226.  
  227.      n2 = malloc(sizeof(struct entry));      /* Insert after. */
  228.      TAILQ_INSERT_AFTER(&head, n1, n2, entries);
  229.  
  230.      n2 = malloc(sizeof(struct entry));      /* Insert before. */
  231.      TAILQ_INSERT_BEFORE(n1, n2, entries);
  232.                                              /* Forward traversal. */
  233.      for (np = head.tqh_first; np != NULL; np = np->entries.tqe_next)
  234.              np-> ...
  235.                                              /* Delete. */
  236.      while (head.tqh_first != NULL)
  237.              TAILQ_REMOVE(&head, head.tqh_first, entries);
  238.  
  239. CCIIRRCCUULLAARR QQUUEEUUEESS
  240.      A circular queue is headed by a structure defined by the CCIIRRCCLLEEQQ__HHEEAADD
  241.      macro.  This structure contains a pair of pointers, one to the first ele-
  242.      ment in the circular queue and the other to the last element in the cir-
  243.      cular queue.  The elements are doubly linked so that an arbitrary element
  244.      can be removed without traversing the queue.  New elements can be added
  245.      to the queue after an existing element, before an existing element, at
  246.      the head of the queue, or at the end of the queue.  A _C_I_R_C_L_E_Q___H_E_A_D struc-
  247.      ture is declared as follows:
  248.  
  249.            CIRCLEQ_HEAD(HEADNAME, TYPE) head;
  250.  
  251.      where HEADNAME is the name of the structure to be defined, and TYPE is
  252.      the type of the elements to be linked into the circular queue.  A pointer
  253.      to the head of the circular queue can later be declared as:
  254.  
  255.            struct HEADNAME *headp;
  256.  
  257.      (The names head and headp are user selectable.)
  258.  
  259.      The macro CCIIRRCCLLEEQQ__EENNTTRRYY declares a structure that connects the elements
  260.      in the circular queue.
  261.  
  262.      The macro CCIIRRCCLLEEQQ__IINNIITT initializes the circular queue referenced by _h_e_a_d.
  263.  
  264.  
  265.      The macro CCIIRRCCLLEEQQ__IINNSSEERRTT__HHEEAADD inserts the new element _e_l_m at the head of
  266.      the circular queue.
  267.  
  268.      The macro CCIIRRCCLLEEQQ__IINNSSEERRTT__TTAAIILL inserts the new element _e_l_m at the end of
  269.      the circular queue.
  270.  
  271.      The macro CCIIRRCCLLEEQQ__IINNSSEERRTT__AAFFTTEERR inserts the new element _e_l_m after the ele-
  272.      ment _l_i_s_t_e_l_m.
  273.  
  274.      The macro CCIIRRCCLLEEQQ__IINNSSEERRTT__BBEEFFOORREE inserts the new element _e_l_m before the
  275.      element _l_i_s_t_e_l_m.
  276.  
  277.      The macro CCIIRRCCLLEEQQ__RREEMMOOVVEE removes the element _e_l_m from the circular queue.
  278.  
  279. CCIIRRCCUULLAARR QQUUEEUUEE EEXXAAMMPPLLEE
  280.      CIRCLEQ_HEAD(circleq, entry) head;
  281.      struct circleq *headp;                  /* Circular queue head. */
  282.      struct entry {
  283.              ...
  284.              CIRCLEQ_ENTRY entries;          /* Circular queue. */
  285.              ...
  286.      } *n1, *n2, *np;
  287.  
  288.      CIRCLEQ_INIT(&head);                    /* Initialize the circular queue. */
  289.  
  290.      n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
  291.      CIRCLEQ_INSERT_HEAD(&head, n1, entries);
  292.  
  293.      n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
  294.      CIRCLEQ_INSERT_TAIL(&head, n1, entries);
  295.  
  296.      n2 = malloc(sizeof(struct entry));      /* Insert after. */
  297.      CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
  298.  
  299.      n2 = malloc(sizeof(struct entry));      /* Insert before. */
  300.      CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
  301.                                              /* Forward traversal. */
  302.      for (np = head.cqh_first; np != (void *)&head; np = np->entries.cqe_next)
  303.              np-> ...
  304.                                              /* Reverse traversal. */
  305.      for (np = head.cqh_last; np != (void *)&head; np = np->entries.cqe_prev)
  306.              np-> ...
  307.                                              /* Delete. */
  308.      while (head.cqh_first != (void *)&head)
  309.              CIRCLEQ_REMOVE(&head, head.cqh_first, entries);
  310.  
  311. HHIISSTTOORRYY
  312.      The qquueeuuee functions first appeared in 4.4BSD.
  313.  
  314. 4th Berkeley Distribution        June 15, 1998                               5
  315.